package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 1/12/21 11:20 AM
 */
public class _148_排序链表_自底向上合并 {


    public ListNode sortList(ListNode head) {

        if (head == null || head.next == null) {

            return head;
        }
        ListNode dummyHead = new ListNode();
        dummyHead.next = head;

        int len = 0;

        while (head != null) {

            len++;
            head = head.next;
        }

        ListNode preNext, node;
        for (int size = 1; size < len; size<<=1) {

            preNext = dummyHead;
            node = dummyHead.next;
            while (node != null) {

                ListNode h1 = node;
                for (int i = 1; i < size && node != null; i++) {

                    node = node.next;
                }

                ListNode tmp = null;
                if (node != null) {

                    tmp = node.next;
                    node.next = null;
                }
                node = tmp;
                ListNode h2 = node;

                for (int i = 1; i < size && node != null; i++) {

                    node = node.next;
                }

                tmp = null;

                if (node != null) {

                    tmp = node.next;
                    node.next = null;
                }
                node = tmp;

                // merge
                ListNode newHead = merge(h1, h2);

                preNext.next = newHead;

                while (newHead != null && newHead.next != null) {

                    newHead = newHead.next;
                }

                preNext = newHead;

            }

        }

        return dummyHead.next;
    }

    private ListNode merge(ListNode h1, ListNode h2) {

        ListNode dummyHead = new ListNode();
        ListNode tail = dummyHead;

        while (h1 != null) {

            if (h2 != null && h1.val > h2.val) {

                tail.next = h2;
                tail = h2;
                h2 = h2.next;
            }else {

                tail.next = h1;
                tail = h1;
                h1 = h1.next;
            }
        }

        if (h2 != null) {

            tail.next = h2;
        }

        return dummyHead.next;
    }

    public static void main(String[] args) {


        ListNode root = ListNode.general(new int[]{4,19,14,5,-3,1,8,5,11,15});

        _148_排序链表_自底向上合并 sortList = new _148_排序链表_自底向上合并();

        ListNode sortRoot = sortList.sortList(root);

        System.out.println(sortRoot);
    }
}
